﻿/*
 * @autor: hectorea
 * @date: 31/07/12
 * @project: MergeSortedArrays
 * 
 */

namespace Merge2SortedArrays
{
    internal class MergeSortedArrays
    {
        /// <summary>
        /// Merge two sorted arrays in one sorted array using temporal array
        /// </summary>
        /// <param name="array1">Sorted Integer Array</param>
        /// <param name="array2">Sorted Integer Array</param>
        /// <returns>One sorted merged array</returns>
        public static int[] Merge(int[] array1, int[] array2)
        {
            //Temporal array to store the result
            int[] merged = new int[array1.Length + array2.Length];

            int i = 0, j = 0, k = 0;

            while (k<merged.Length)
            {
                //if both arrays are in boundaries
                if (i < array1.Length && j < array2.Length)
                {
                    //check which value is lesser and it's stored it in the current position of k
                    if (array1[i] < array2[j])
                        merged[k++] = array1[i++];
                    else 
                        merged[k++] = array2[j++];
                }
                else if (i < array1.Length)     //if just leave array1
                    merged[k++] = array1[i++];
                else if (j < array2.Length)     //if just leave array1
                    merged[k++] = array2[j++];
            }
            
            return merged;
        }

        /// <summary>
        /// Merge two sorted arrays in one sorted array without using temporal array
        /// </summary>
        /// <param name="array1">Sorted Integer Array</param>
        /// <param name="array2">Sorted Integer Array</param>
        /// <returns>One sorted merged array</returns>
        internal static int[] MergeWithoutAdditionalArray(int[] array1, int[] array2)
        {
            int i = array2.Length-1;    
            int j = array2.Length - 1;
            int k = array1.Length-1;

            while (k>=1)
            {
                //if we are inside the boundaries of array1 and array2
                if (i >= 0 && j >= 0)
                {
                    //check which have the greater value and it's stored in the current position of k
                    if (array1[i] > array2[j])
                        array1[k--] = array1[i--];
                    else
                        array1[k--] = array2[j--];
                }
                else if (i >= 0)
                    array1[k--] = array1[i--];      //if just leave array1
                else if (j >= 0)
                    array1[k--] = array2[j--];      //if just leave array2                
            }

            return array1;
        }
        
        /// <summary>
        /// Helper function to resize an array
        /// </summary>
        /// <param name="array1"></param>
        /// <param name="array2"></param>
        /// <returns></returns>
        private static int[] ResizeHelper(int[] array1, int[] array2)
        {
            int count = 0;
            int[] output = new int[array1.Length + array2.Length];

            for (int i = 0; i < array1.Length; i++)
                output[count++] = array1[i];           

            return output;
        }        
    }
}
